package tree

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 var res []*TreeNode

func generateTrees(n int) []*TreeNode {
    // 本质是对一个有序数组找分隔点
    
}
func gt(left []int,root *TreeNode right []int,res []*TreeNode,rt *TreeNode){
    if len(left) <2 && left(right) <2{
        if len(left) ==1 {
            root.Left = &TreeNode{left[0],nil,nil}
        }
        if len(right) == 1 {
            root.Right = &TreeNode{right[0],nil,nil}
        }
        // 此时一棵树构造完毕，要记录结果
        // 如何保存结果？
        // 因为这棵树会被覆盖，所以再复制一棵树


        return
    }
    if len(left) > 1 {
        for i,val :=range left{
            // root.Left有不同的选择
            root.Left = &TreeNode{val,nil,nil}
            gt(left[0:i],root.Left,left[i+1:])
        }
    }
    if len(right) > 1 {
        for i,val:=range right{
            root.Right = &TreeNode{val,nil,nil}
            gt(right[0:i],root.Right,right[i+1:])
        }
    }
}
/**
 复制一个棵二叉树，
 大概也是沿着其访问轨迹,逐个复制
 在比如判断两颗数是否对称的
*/
func copyTree(root *TreeNode) *TreeNode{
    var root2 *TreeNode
    stack:=make([]*TreeNode,0)
    for root!=nil || len(stack)>0{
        if root!=nil{
            root2 := &TreeNode{root.Val,nil,nil}
            stack=append(stack,root)
            root = root.left
		
        }
        
    }
	return root2
}
